\documentclass[twoside,a4paper]{ctexart}
\usepackage{geometry}
\geometry{margin=1.5cm, vmargin={0pt,1cm}}
\setlength{\topmargin}{-1cm}
\setlength{\paperheight}{29.7cm}
\setlength{\textheight}{25.3cm}

% useful packages.
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{enumerate}
\usepackage{graphicx}
\usepackage{multicol}
\usepackage{fancyhdr}
\usepackage{layout}

% some common command
\newcommand{\dif}{\mathrm{d}}
\newcommand{\avg}[1]{\left\langle #1 \right\rangle}
\newcommand{\difFrac}[2]{\frac{\dif #1}{\dif #2}}
\newcommand{\pdfFrac}[2]{\frac{\partial #1}{\partial #2}}
\newcommand{\OFL}{\mathrm{OFL}}
\newcommand{\UFL}{\mathrm{UFL}}
\newcommand{\fl}{\mathrm{fl}}
\newcommand{\op}{\odot}
\newcommand{\Eabs}{E_{\mathrm{abs}}}
\newcommand{\Erel}{E_{\mathrm{rel}}}

\begin{document}

\pagestyle{fancy}
\fancyhead{}
\lhead{邵柯欣 (3200103310)}
\chead{Data Modeling homework \#2.1 \& 2.3}
\rhead{\today}


\section*{I. （2.1）验证感知机不能表示异或}

\subsection*{证明：}
取四个例点$X_1 = (0,0),X_2 = (1,1),X_3 = (1,0),X_4 = (0,1)$.

由异或的真值表可知$y_1 = 1,y_2 = 1,y_3 = -1, y_4 = -1$.

若该例点集可线性分离，则存在$f = WX^T+ b$为对应的线性模型，其中$W = (w_1,w_2)$.

\begin{equation}
  \because \quad f(X_1) > 0,f(X_2) > 0.\notag
\end{equation}
\begin{equation}
  \therefore \quad
  \left\{
  \begin{matrix}
  0 + 0 + b > 0 \\
  w_1 + w_2 + b > 0
  \end{matrix}
  \right.
  \Longrightarrow
  w_1+w_2+2b > 0 \label{eq::01}
\end{equation}

\begin{equation}
  \because \quad f(X_3) < 0,f(X_4) < 0.\notag
\end{equation}
\begin{equation}
  \therefore \quad
  \left\{
  \begin{matrix}
  w_1 + 0 + b < 0 \\
  0 + w_2 + b < 0
  \end{matrix}
  \right.
  \Longrightarrow
  w_1+w_2+2b < 0 \label{eq::02}
\end{equation}

$\therefore \quad $(\ref{eq::01})与(\ref{eq::02})矛盾，感知机不能表示异或.

\section*{II. （2.3）证明：样本集线性可分的充分必要条件是正实例点集所构成的凸壳与负实例点集所构成的凸壳互不相交}

\subsection*{证明：}
$''\Longleftarrow'':\quad \because \quad$正负实例点集构成的凸壳互不相交.

$\therefore \quad$存在一个超平面将两个凸壳线性分开.

$\because \quad$由凸壳的定义知，正（负）实例点一定在正（负）实例点集构成的凸壳内.

$\therefore \quad$该超平面也能将正负实例点集线性分开.

~\\

$''\Longrightarrow'': \quad$设A、B为正负实例点集，$y_A = 1,y_B = -1$.

$\because \quad$A、B线性可分，设分割A、B的超平面为$f = wx+b$.

$\therefore \quad$
\begin{equation}
  \left\{
\begin{matrix}
  \forall x \in A, wx+b > 0 \\
  \forall x \in B, wx+b < 0
\end{matrix}\label{eq::03}
\right.
\end{equation}

凸壳相交，不妨设存在$x \in A$且$x \in conv(B)$.

$x$可以被B中的点进行凸组合表示，即$x = \sum^N_{j = 1}\lambda_jx_j \quad (x_j \in B)$.

\begin{align}
  wx+b &= w\sum^N_{j = 1}\lambda_jx_j + b \notag\\
  &= \sum^N_{j = 1}\lambda_jwx_j + \sum^N_{j = 1}\lambda_jb \notag\\
  &= \sum^N_{j = 1}\lambda_j(wx_j+b) < 0 \notag
\end{align}

与(\ref{eq::03})中$wx+b > 0 \quad (\forall x \in A)$矛盾.

$\therefore \quad conv(A)$与$conv(B)$一定不相交.
\end{document}
